package com.example.dynamicplanning;

import com.alibaba.fastjson.JSON;

/**
 * 背包问题
 * <p>
 * 我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
 * for(int i = 0; i < weight.size(); i++) { // 遍历物品
 * for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
 * dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
 * }
 * }
 * <p>
 * 而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：
 * // 先遍历物品，再遍历背包
 * for(int i = 0; i < weight.size(); i++) { // 遍历物品
 * for(int j = weight[i]; j < bagWeight ; j++) { // 遍历背包容量
 * dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
 * }
 * }
 * 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
 * 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
 */
public class PackProblem {
    public static void main(String[] args) {
        int[] weight = {1, 2, 3};
        int[] value = {15, 20, 30};
        int bagweight = 4;
        //dp[i][j] 表示从下标为[0-i]的物品⾥任意取，放进容量为j的背包，价值总和最⼤是多少。
        int[][] dp = new int[weight.length][bagweight + 1];

        for (int j = bagweight; j >= weight[0]; j--) {
            dp[0][j] = dp[0][j - weight[0]] + value[0];
        }

        for (int i = 1; i < weight.length; i++) {
            for (int j = 0; j <= bagweight; j++) {
                if (j < weight[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i] + value[i]]);
                }
            }
        }
        System.out.println(JSON.toJSONString(dp));
    }
}


/**
 * 494. 目标和---01背包
 * 给你一个整数数组 nums 和一个整数 target 。
 * <p>
 * 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 * <p>
 * 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,1,1,1,1], target = 3
 * 输出：5
 * 解释：一共有 5 种方法让最终目标和为 3 。
 * -1 + 1 + 1 + 1 + 1 = 3
 * +1 - 1 + 1 + 1 + 1 = 3
 * +1 + 1 - 1 + 1 + 1 = 3
 * +1 + 1 + 1 - 1 + 1 = 3
 * +1 + 1 + 1 + 1 - 1 = 3
 * <p>
 * 思路：
 * 01背包问题是选或者不选，但本题是必须选，是选+还是选-。先将本问题转换为01背包问题。
 * 假设所有符号为+的元素和为x，符号为-的元素和的绝对值是y。
 * 我们想要的 S = 正数和 - 负数和 = x - y
 * 而已知x与y的和是数组总和：x + y = sum
 * 可以求出 x = (S + sum) / 2 = target
 * 也就是我们要从nums数组里选出几个数，令其和为target
 * 于是就转化成了求容量为target的01背包问题 =>要装满容量为target的背包，有几种方案
 * 特例判断
 * 如果S大于sum，不可能实现，返回0
 * 如果x不是整数，也就是S + sum不是偶数，不可能实现，返回0
 * dp[j]代表的意义：填满容量为j的背包，有dp[j]种方法。因为填满容量为0的背包有且只有一种方法，所以dp[0] = 1
 * 状态转移：dp[j] = dp[j] + dp[j - num]，
 * 当前填满容量为j的包的方法数 = 之前填满容量为j的包的方法数 + 之前填满容量为j - num的包的方法数
 * 也就是当前数num的加入，可以把之前和为j - num的方法数加入进来。
 * 返回dp[-1]，也就是dp[target]
 */
class findTargetSumWays {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (S > sum || (S + sum) % 2 == 1) return 0;
        int bagsize = (S + sum) / 2;
        int[] dp = new int[bagsize + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = bagsize; j >= num; j--) {
                //在求装满背包有⼏种⽅法的情况下
                dp[j] = dp[j] + dp[j - num];
            }
        }
        return dp[bagsize];
    }
}